package graphPath;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import javax.xml.bind.annotation.XmlType.DEFAULT;

import org.jgrapht.WeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class BreadthFirstSearch {

	public Map <Integer, Integer> vertex_color;

	
	
	public BreadthFirstSearch(){
		vertex_color = new HashMap<Integer, Integer>();

		
	}
	
	public void initial(WeightedGraph<String, DefaultWeightedEdge> graph){
		
		

		List<Integer> vertices = new ArrayList<Integer>();
		
				for(String element : graph.vertexSet()){
							
					int vertex= Integer.parseInt(element);
					vertices.add(vertex);
					vertex_color.put(vertex, Color.white);			
									
				}
		
				Collections.sort(vertices);
				

				
				for(Integer vertex : vertices){
					
						if(vertex_color.get(vertex)== Color.white){
							
							bfs(graph, vertex);
							
						}
							
				}
		
	}
	
	public List<Integer> bfs(WeightedGraph<String, DefaultWeightedEdge> graph, int vertex){
		List<Integer> order = new ArrayList<Integer>();
		Queue<Integer> queue = new LinkedList <Integer>();
		
		
		int first = 0;
		

		vertex_color.put(vertex, Color.gray);

		
		queue.add(vertex);
		

		while(queue.size()> 0){
			
			first= queue.peek();
			
			order.add(first);
			queue.remove();
			
			

		
			for(Integer element : getNeighborSet(graph,first) ){
				if(vertex_color.get(element)== Color.white){
					vertex_color.put(element, Color.gray);
					

					
					queue.add(element);
				}
			}
		
			
		}
		System.out.println("Breadth First Search Traversal: " + order);
		return order;
	}
	
	
	
	
	
	
	//find the neighborSet of specific vertex
		public List<Integer> getNeighborSet(final WeightedGraph <String, DefaultWeightedEdge> graph, int v){
			
			List <String> neighbor = new ArrayList <String> ();
			List <Integer> result = new ArrayList <Integer> ();

			List<DefaultWeightedEdge> weightedEdges = new ArrayList<DefaultWeightedEdge>(graph.edgesOf(String.valueOf(v)));
			
			//Sort edges by weight
			Collections.sort(weightedEdges, new Comparator<DefaultWeightedEdge>() {

				@Override
				public int compare(DefaultWeightedEdge o1, DefaultWeightedEdge o2) {
					return Double.valueOf(graph.getEdgeWeight(o1)).compareTo(
							Double.valueOf(graph.getEdgeWeight(o2)));
				}
			});
			
			
			for( DefaultWeightedEdge element : weightedEdges){
				
							
				if(graph.getEdgeSource(element).equals(String.valueOf(v)) ){
					neighbor.add(graph.getEdgeTarget(element));
				
								
				}else{
					neighbor.add(graph.getEdgeSource(element));
				}
			}
			
			for(String element: neighbor){
				result.add(Integer.parseInt(element));
			}
			
			
			
//			System.out.println(result);
			return result;
			
			
		}
	
	
	
		
			
		
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		WeightedGraph <String, DefaultWeightedEdge> graph =
//				 new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
//		
//		
//				 String v0 = "0";
//				 String v1 = "1";
//				 String v2 = "2";
//				 String v3 = "3";
//				 String v4 = "4";
//				 
//				 graph.addVertex(v1);
//				 graph.addVertex(v2);
//				 graph.addVertex(v3);
//				 graph.addVertex(v4);
//				 graph.addVertex(v0);
//			
//				 
//				 DefaultWeightedEdge e1 = graph.addEdge(v0, v2);
//				 DefaultWeightedEdge e2 = graph.addEdge(v0, v3);
//				 DefaultWeightedEdge e3 = graph.addEdge(v0, v4);
//				 DefaultWeightedEdge e4 = graph.addEdge(v1, v2);
//				 DefaultWeightedEdge e5 = graph.addEdge(v1, v3);
//				 DefaultWeightedEdge e6 = graph.addEdge(v2, v3);
//				 DefaultWeightedEdge e7 = graph.addEdge(v2, v4);
//				 
//				 
//				 graph.setEdgeWeight(e1, 3.0);
//				 graph.setEdgeWeight(e2, 2.1);
//				 graph.setEdgeWeight(e3, 4.3);
//				 graph.setEdgeWeight(e4, 3.14);
//				 graph.setEdgeWeight(e5, 2.5);
//				 graph.setEdgeWeight(e6, 3.9);
//				 graph.setEdgeWeight(e7, 10.3);
//				 
//				 
//				 System.out.println(graph);
//				 BreadthFirstSearch bfs = new BreadthFirstSearch();
//				 bfs.initial(graph);
				 
				 
				 
	}

}
